// StrokeData.cpp: implementation of the CStrokeData class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "StrokeData.h"
#include "LinePoint.h"
#include <memory.h>

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

///////////////////////////////////////////////////////////////////////////////

#ifdef SafeDelete
#undef SafeDelete
#endif	// SafeDelete

#define SafeDelete(p) if(p){delete[] p; p=NULL;}

#ifdef SafeRemove
#undef SafeRemove
#endif	// SafeRemove

#define SafeRemove(p) if(p){delete p;p=NULL;}

///////////////////////////////////////////////////////////////////////////////

//#define SIMPLE_KEYPOINT

#ifndef SIMPLE_KEYPOINT
#include "ParseStrokeKeyPoint.h"
#endif	// SIMPLE_KEYPOINT

///////////////////////////////////////////////////////////////////////////////

const float EPSILON = 1.0e-5f;
const float PI = 3.141592653589793f;

///////////////////////////////////////////////////////////////////////////////
// constructions

SCoverFlag::SCoverFlag()
{
	m_pbFlag = NULL;
	m_nMinX = 0;
	m_nMinY = 0;
	m_nMaxW = 0;
	m_nMaxH = 0;
}

SCoverFlag::~SCoverFlag()
{
	destruct();
}

///////////////////////////////////////////////////////////////////////////////

int SCoverFlag::destruct(void)
{
	ASSERT(this != NULL);
	SafeDelete(m_pbFlag);
	return 0;
}

int SCoverFlag::getLargeCoverCount(int xCheck, int yCheck) const
{
	ASSERT(this != NULL);
	ASSERT(xCheck>0 && yCheck>0);
	ASSERT(xCheck<=0x0f && yCheck<=0x0f);
	int nCount = 0;
	int yT = (yCheck << 4);
	int nMax = m_nMaxW * m_nMaxH;
	for(int i=0; i<nMax; i++) {
		if ((m_pbFlag[i] & 0x0f) >= xCheck &&
			(m_pbFlag[i] & 0xf0) >= yT)
			nCount++;
	}
	return nCount;
}

BOOL SCoverFlag::initFromRect(const RECT *lpRect)
{
	ASSERT(this != NULL);
	if (!lpRect || lpRect->left>lpRect->right || lpRect->top>lpRect->bottom)
		return FALSE;
	m_nMinX = lpRect->left;
	m_nMinY = lpRect->top;
	m_nMaxW = lpRect->right - lpRect->left + 1;
	m_nMaxH = lpRect->bottom - lpRect->top + 1;
	destruct();
	return TRUE;
}

BOOL SCoverFlag::setFlagFromPoint(const SPoint *lpPoint, int nPoint)
{
	ASSERT(this != NULL);
	if (!lpPoint || nPoint<=0 || m_nMaxW<=0 || m_nMaxH<=0)
		return FALSE;
	if (!m_pbFlag && (m_pbFlag=new BYTE[m_nMaxW * m_nMaxH])==NULL)
		return FALSE;
	memset(m_pbFlag, 0, m_nMaxW * m_nMaxH);

	int x, y, x0, y0;
	int xLast = lpPoint[0].x;
	int yLast = lpPoint[0].y;
	addXFlag(xLast);
	addYFlag(yLast);
	for(int i=1; i<nPoint; i++) {
		/////////////////////
		x0 = lpPoint[i].x;
		int x1 = min(x0, xLast);
		int x2 = max(x0, xLast);
		for(x=x1; x<=x2; x++) {
			if (x != xLast)
				addXFlag(x);
		}
		/////////////////////
		y0 = lpPoint[i].y;
		int y1 = min(y0, yLast);
		int y2 = max(y0, yLast);
		for(y=y1; y<=y2; y++) {
			if (y != yLast)
				addYFlag(y);
		}
		/////////////////////
		xLast = x0;
		yLast = y0;
	}
	return TRUE;
}

///////////////////////////////////////////////////////////

BOOL SCoverFlag::addXFlag(int x)
{
	if (!m_pbFlag || x<m_nMinX || x>=m_nMinX+m_nMaxW)
		return FALSE;
	for(int y=0; y<m_nMaxH; y++) {
		BYTE& b = m_pbFlag[m_nMaxW * y + x - m_nMinX];
		if ((b & 0x0f) < 0x0f)
			b++;
	}
	return TRUE;
}

BOOL SCoverFlag::addYFlag(int y)
{
	if (!m_pbFlag || y<m_nMinY || y>=m_nMinY+m_nMaxH)
		return FALSE;
	int nBase = m_nMaxW * (y - m_nMinY);
	for(int x=0; x<m_nMaxW; x++) {
		BYTE& b = m_pbFlag[nBase + x];
		if ((b & 0xf0) < 0xf0)
			b += 0x10;
	}
	return TRUE;
}

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CStrokeData::CStrokeData()
{
	m_lpSrcPoint = NULL;
	m_nSrcPoint = 0;

	m_nPoint = 0;
	m_eIndex = INDEX_ERROR;
	m_fLength = 0.0f;
	m_fSingleDian = FALSE;
	m_nCurveType = 0;

	m_pNext = NULL;
}

CStrokeData::~CStrokeData()
{
	destruct();
}

BOOL CStrokeData::createReducePoint(int cx, int cy, BOOL *pfStop, BOOL fSkipCircle, void *lpContext)
{
	ASSERT(this != NULL);
	if (!m_lpSrcPoint || m_nSrcPoint<=0)
		return FALSE;
	if (m_nSrcPoint == 1) {
		m_ptBuf[0] = m_lpSrcPoint[0];
		m_nPoint = 1;
		return TRUE;
	}
	SPoint ptCenter;
	RECT rectMax;
	if (fSkipCircle && locateCirclePoint(&ptCenter, &rectMax)) {
		m_ptBuf[0] = ptCenter;
		m_nPoint = 1;
		m_eIndex = INDEX_CIRCLE;
		return TRUE;
	}
#ifdef SIMPLE_KEYPOINT
	m_nPoint = createSimplePoints(m_ptBuf, MAX_KEYPOINT, &rectMax);
	UNREFERENCED_PARAMETER(cx);
	UNREFERENCED_PARAMETER(cy);
	UNREFERENCED_PARAMETER(pfStop);
#else
	SIZE size = {cx, cy};
	CParseStrokeKeyPoint parsePoint;
	parsePoint.m_nDistanceMethod = 6;
	parsePoint.m_bFastAlgorithm = FALSE;
	parsePoint.setAllPoint(m_lpSrcPoint, m_nSrcPoint, &size);
	if (lpContext != NULL)
		parsePoint.enableCheckInContour((CCheckInContour *)lpContext);
	m_nPoint = parsePoint.createBestPointList(m_ptBuf, MAX_KEYPOINT, pfStop);
#endif	// SIMPLE_KEYPOINT
	return (m_nPoint > 0);
}

BOOL CStrokeData::locateCirclePoint(SPoint *lpCenter, RECT *lpMaxRect)
{
	ASSERT(this != NULL);
	m_nCurveType = 0;
	SLinePoint lp;
	lp.m_lpPoint = m_lpSrcPoint;
	lp.m_nPoint = m_nSrcPoint;
	RECT r;
	lp.getMaxRect(&r);
	m_fLength = lp.getSumLength();
	*lpMaxRect = r;
	// to check whether length is too long or not
	int x, y;
	int nMaxW = r.right - r.left + 1;
	int nMaxH = r.bottom - r.top + 1;
	int nBase = 3 * nMaxW + nMaxH;
	if (m_fLength > nBase + min(r.right-r.left+1, r.bottom-r.top+1)*0.5f) {
		x = (r.left + r.right) / 2;
		y = (r.top + r.bottom) / 2;
		lpCenter->x = (short)x;
		lpCenter->y = (short)y;
		return TRUE;
	}
	// to use projection area to judge circle lines...
	SCoverFlag cf;
	cf.initFromRect(&r);
	cf.setFlagFromPoint(m_lpSrcPoint, m_nSrcPoint);
	int nCount = cf.getLargeCoverCount(2, 2);
	int nCount3 = cf.getLargeCoverCount(3, 1);
	if (2 * nCount3 >= nMaxW * nMaxH)
		m_nCurveType = 2;
	if (m_nCurveType == 0) {
		int nCount2 = cf.getLargeCoverCount(2, 1);
		if (nCount2 >= nMaxW * nMaxH * 0.7f)
			m_nCurveType = 1;
	}
	if (2 * nCount >= nMaxW * nMaxH) {
		x = (r.left + r.right) / 2;
		y = (r.top + r.bottom) / 2;
		lpCenter->x = (short)x;
		lpCenter->y = (short)y;
		return TRUE;
	}
	return FALSE;
}

float CStrokeData::getSrcPointLength(void) const
{
	int i;
	ASSERT(this != NULL);
	if (m_nSrcPoint == 1)
		return 1.0f;
	float fSumLength = 0;
	for(i=1; i<m_nSrcPoint; i++) {
		int dx = m_lpSrcPoint[i].x - m_lpSrcPoint[i-1].x;
		int dy = m_lpSrcPoint[i].y - m_lpSrcPoint[i-1].y;
		fSumLength += sqrtf(dx * dx + dy * dy + 0.0f);
	}
	return fSumLength;
}

int CStrokeData::checkGouTiType(void) const
{
	ASSERT(this != NULL);
	if (!m_lpSrcPoint || m_nSrcPoint<=2)
		return 0;
	int x = m_lpSrcPoint[m_nSrcPoint - 1].x;
	int y = m_lpSrcPoint[m_nSrcPoint - 1].y;
	for(int i=m_nSrcPoint-2; i>=0; i--) {
		if (m_lpSrcPoint[i].y > y)
			continue;
		if (m_lpSrcPoint[i].y == y) {
			if (m_lpSrcPoint[i].x < x)
				return 2;	// Ti
			if (x < m_lpSrcPoint[i].x)
				return 1;	// Gou
		}
		float xCheck = m_lpSrcPoint[i+1].x + (m_lpSrcPoint[i+1].y - y) * (m_lpSrcPoint[i].x - m_lpSrcPoint[i+1].x) / (m_lpSrcPoint[i+1].y - m_lpSrcPoint[i].y + 0.0f);
		if (xCheck < x - EPSILON)
			return 2;	// Ti
		if (x < xCheck + EPSILON)
			return 1;	// Gou
		return 0;
	}
	return 0;
}

void CStrokeData::destruct(void)
{
	ASSERT(this != NULL);
	SafeDelete(m_lpSrcPoint);
	SafeRemove(m_pNext);
}

///////////////////////////////////////////////////////////////////////////////

const int BUF_SIZE = 64;
int CStrokeData::createInitialCandIndex(DWORD *dwCandIndex, int nMax, const SPoint *lpPoint, int nPoint) const
{
	int i, m, nBuf[BUF_SIZE];
	int *pnValue = nBuf;
	if (nPoint>BUF_SIZE && (pnValue = new int[nPoint])==NULL)
		return 0;
	for(i=0; i<nPoint; i++)
		pnValue[i] = lpPoint[i].x - lpPoint[i].y;
	int nCandCount = 1;
	int nLastType = (pnValue[0]<=pnValue[1] ? 1 : 2);
	dwCandIndex[0] = MAKELONG(0, nLastType);
	int nLastValue = pnValue[0];
	for(i=1; i+1<nPoint && nCandCount<nMax; i++) {
		m = pnValue[i];
		if (m<pnValue[i-1] && m<=pnValue[i+1]) {
			if (nLastType==2 && abs(nLastValue-m)<=2) {
				NULL;
			} else if (nCandCount>1 && nLastType==1 && m<=nLastValue && m>=nLastValue-2) {
				dwCandIndex[nCandCount-1] = MAKELONG(i, 1);
				nLastType = 1;
				nLastValue = m;
			} else if (nLastType==1 && nLastValue<m && m-nLastValue<=2) {
				NULL;
			} else {
				dwCandIndex[nCandCount++] = MAKELONG(i, 1);
				nLastType = 1;
				nLastValue = m;
			}
		} else if(m>pnValue[i-1] && m>=pnValue[i+1]) {
			if (nLastType==1 && abs(nLastValue-m)<=2) {
				NULL;
			} else if (nCandCount>1 && nLastType==2 && m>=nLastValue && m<=nLastValue+2) {
				dwCandIndex[nCandCount-1] = MAKELONG(i, 2);
				nLastType = 2;
				nLastValue = m;
			} else if (nLastType==2 && nLastValue>m && nLastValue-m<=2) {
				NULL;
			} else {
				dwCandIndex[nCandCount++] = MAKELONG(i, 2);
				nLastType = 2;
				nLastValue = m;
			}
		} else if(m_nCurveType != 0) {
			if ((m_nCurveType==2 && lpPoint[i].x<=lpPoint[i-1].x && lpPoint[i].x<lpPoint[i+1].x) ||
				(m_nCurveType==1 && lpPoint[i].x>lpPoint[i-1].x && lpPoint[i].x>=lpPoint[i+1].x) ||
				(m_nCurveType==1 && lpPoint[i].x>=lpPoint[i-1].x && lpPoint[i].x>lpPoint[i+1].x)) {
				dwCandIndex[nCandCount++] = MAKELONG(i, 3);
				nLastType = 3;
				nLastValue = m;
			}
		}
	}
	if (pnValue != nBuf)
		delete[] pnValue;
	return nCandCount;
}

/// cos( 20 degree )
const float fCosineThreshold = cosf(PI / 9);
int CStrokeData::updateCandIndexFromLargeAnglePoint(DWORD *dwCandIndex, int nCandCount, int nMaxSize, const SPoint *lpPoint) const
{
	int m, n;
	for(int k=0; k+1<nCandCount; k++) {
		n = LOWORD(dwCandIndex[k+1]);
		int n0 = LOWORD(dwCandIndex[k]);
		if (n == n0+1)
			continue;
		int dx = lpPoint[n].x - lpPoint[n0].x;
		int dy = lpPoint[n].y - lpPoint[n0].y;
		if (abs(dx)>=6 || abs(dy)>=6) {
			int nMax = 0;
			int nMaxIdx = n0;
			for(int i=n0+1; i<n; i++) {
				m = abs(dy * (lpPoint[i].x - lpPoint[n0].x) - dx * (lpPoint[i].y - lpPoint[n0].y));
				if (nMaxIdx<0 || nMax<m) {
					nMaxIdx = i;
					nMax = m;
				}
			}
			if (n0 < nMaxIdx) {
				int dx1 = lpPoint[nMaxIdx].x - lpPoint[n0].x;
				int dy1 = lpPoint[nMaxIdx].y - lpPoint[n0].y;
				int dx2 = lpPoint[n].x - lpPoint[nMaxIdx].x;
				int dy2 = lpPoint[n].y - lpPoint[nMaxIdx].y;
				if ((abs(dx1)>2 || abs(dy1)>2) && (abs(dx2)>2 || abs(dy2)>2)) {
					float fCosine = (dx1 * dx2 + dy1 * dy2) / sqrtf(dx1 * dx1 + dy1 * dy1 + EPSILON) / sqrtf(dx2 * dx2 + dy2 * dy2 + EPSILON);
					if (fCosine < fCosineThreshold) {
						// insert at position 1
						for(n=min(nCandCount, nMaxSize-1); n>k+1; n--)
							dwCandIndex[n] = dwCandIndex[n-1];
						dwCandIndex[k+1] = nMaxIdx;
						nCandCount = n + 1;
						k++;
					}
				}
			}
		}
	}
	return nCandCount;
}

BOOL CStrokeData::getMinMaxRect(RECT *lpRect, const SPoint *lpPoint, int nPoint)
{
	if (!lpRect || !lpPoint || nPoint<2)
		return FALSE;
	int x = lpPoint->x;
	int y = lpPoint->y;
	RECT rect = {x, y, x, y};
	for(int i=1; i<nPoint; i++) {
		x = lpPoint[i].x;
		y = lpPoint[i].y;
		rect.left = min(rect.left, x);
		rect.right = max(rect.right, x);
		rect.top = min(rect.top, y);
		rect.bottom = max(rect.bottom, y);
	}
	*lpRect = rect;
	return TRUE;
}

int CStrokeData::locateIndexOfHZZP(const SPoint *lpPoint, int nPoint)
{
	// test case: u0001_20130716175221.chn
	SPoint pt0 = lpPoint[0];
	SPoint ptEnd = lpPoint[nPoint-1];
	RECT rect;
	getMinMaxRect(&rect, lpPoint, nPoint);
	// to exclude INDEX_PIE/INDEX_SHU/INDEX_S_ZHE etc.
	int nBestIdx = -1;
	if (pt0.x<rect.right-1 && (ptEnd.x-pt0.x)*3<=(rect.right-pt0.x) &&
		(pt0.y-rect.top)*4<=(rect.bottom-rect.top) && (rect.bottom-ptEnd.y)*4<=(rect.bottom-rect.top)) {
		int x, y;
		int yMin = rect.top + (rect.bottom - rect.top) / 4;
		int yMax = rect.bottom - (rect.bottom - rect.top) / 4;
		for(int i=1; i+1<nPoint; i++) {
			y = lpPoint[i].y;
			if (y<yMin || y>yMax)
				continue;
			x = lpPoint[i].x;
			if (nBestIdx<0 || x<lpPoint[nBestIdx].x)
				nBestIdx = i;
		}
	}
	return nBestIdx;
}

const int MAX_CAND = 10;
int CStrokeData::createCandPoints(SPoint *ptOut, int nOut, const SPoint *lpPoint, int nPoint) const
{
	int i, n;
	ASSERT(nOut >= 6);
	if (nPoint <= 3) {
		memcpy(ptOut, lpPoint, sizeof(SPoint)*nPoint);
		return nPoint;
	}
	// to locate local-min/local-max points for f(x, y)=x-y
	DWORD dwCandIndex[MAX_CAND + 6] = {0};
	int nCandCount = createInitialCandIndex(dwCandIndex, MAX_CAND, lpPoint, nPoint);
	if (/*m_nCurveType==1 && */nCandCount>1)
		nCandCount = updateCandIndexFromLargeAnglePoint(dwCandIndex, nCandCount, MAX_CAND + 6, lpPoint);
	// to locate point for INDEX_GOU
	int nCheckMax = LOWORD(dwCandIndex[nCandCount-1]);
	int x_add_y = lpPoint[nPoint-1].x + lpPoint[nPoint-1].y;
	int nMaxIndex = nPoint-1;
	for(i=nCheckMax; i+1<nPoint; i++) {
		n = lpPoint[i].x + lpPoint[i].y;
		if (n > x_add_y) {
			x_add_y = n;
			nMaxIndex = i;
		}
	}
	if (nCheckMax<nMaxIndex && nMaxIndex<nPoint-1 && nCandCount<MAX_CAND)
		dwCandIndex[nCandCount++] = nMaxIndex;
	// to add the final point
	dwCandIndex[nCandCount++] = nPoint-1;
	// try to locate key point index of INDEX_H_ZZP
	int nBestIdx = locateIndexOfHZZP(lpPoint, nPoint);
	// to output points
	DWORD dwValue;
	int nOutput = 0;
	for(i=0; i<nCandCount && nOutput<nOut; i++) {
		dwValue = dwCandIndex[i];
		n = LOWORD(dwValue);
		if (0<=nBestIdx && nBestIdx<=n) {
			if (nBestIdx < n)
				ptOut[nOutput++] = lpPoint[nBestIdx];
			nBestIdx = -1;
		}
		ptOut[nOutput++] = lpPoint[n];
	}
	return nOutput;
}

int CStrokeData::createSimplePoints(SPoint *ptOut, int nOut, const RECT *lpRect) const
{
	ASSERT(nOut >= 6);
	if (m_nSrcPoint <= 3) {
		memcpy(ptOut, m_lpSrcPoint, sizeof(SPoint)*m_nSrcPoint);
		return m_nSrcPoint;
	}
	int cx = lpRect->right - lpRect->left + 1;
	int cy = lpRect->bottom - lpRect->top + 1;
	int nMaxXY = max(cx, cy);
	if (nMaxXY <= 32)
		return createCandPoints(ptOut, nOut, m_lpSrcPoint, m_nSrcPoint);
	int nRatio = (nMaxXY + 16 - 1) / 16;
	SPoint pt, *ptBuf;
	if ((ptBuf=new SPoint[m_nSrcPoint]) == NULL)
		return 0;
	int i, nBuf = 0;
	for(i=0; i<m_nSrcPoint; i++) {
		pt.x = (short)((m_lpSrcPoint[i].x - lpRect->left) / nRatio);
		pt.y = (short)((m_lpSrcPoint[i].y - lpRect->top) / nRatio);
		// same point
		if (nBuf>0 && ptBuf[nBuf-1].x==pt.x && ptBuf[nBuf-1].y==pt.y)
			continue;
		// same line
		if (nBuf>1 && (pt.y-ptBuf[nBuf-1].y)*(ptBuf[nBuf-1].x-ptBuf[nBuf-2].x)==(pt.x-ptBuf[nBuf-1].x)*(ptBuf[nBuf-1].y-ptBuf[nBuf-2].y))
			ptBuf[nBuf-1] = pt;
		else
			ptBuf[nBuf++] = pt;
	}
	// to find candidate points
	int nRes = createCandPoints(ptOut, nOut, ptBuf, nBuf);
	delete[] ptBuf;
	ptOut[0] = m_lpSrcPoint[0];
	for(i=1; i<nRes; i++) {
		ptOut[i].x = (short)(ptOut[i].x * nRatio + lpRect->left);
		ptOut[i].y = (short)(ptOut[i].y * nRatio + lpRect->top);
	}
	return nRes;
}
